package com.biancheng.biancheng.L2;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 二叉树深度 {

    /**
     *
     题目描述：
     给定一个二叉树，找出其最大深度。
     二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
     说明: 叶子节点是指没有子节点的节点。

     输入描述:
     给定一个二叉树

     输出描述：
     输出最大深度的二叉树排列及二叉树的最大深度

     样例输入：
     [3,9,20,null,null,15,7]

     样例输出：
     3
     / \
     9 20
     / \
     15  7
     二叉树的最大深度： 3
        */
    private static int maxDepth(TreeNode root) {
        // 如果该节点为空则返回0
        if (root == null) {
            return 0;
        }
        // 得到左节点的高度
        int lefti = maxDepth(root.left);
        // 得到右节点的高度
        int righti = maxDepth(root.right);
        // 如果左右孩子存在，则取出最大值加一（根节点默认高度为1）
        // 利用工具类内存占用量更少
        return Math.max(lefti, righti) + 1;
    }


    public static void main(String[] args) {
        System.out.println("请输入一个二叉树：");
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String sArray[] = s.split(",");
        List<TreeNode> list = new ArrayList<>();
        for (int i = 0; i <sArray.length; i++) {
            list.add(new TreeNode(sArray[i]));
        }

         TreeNode root = new TreeNode("3");
         TreeNode t1 = new TreeNode("9");
         TreeNode t2 = new TreeNode("20");
         TreeNode t3 = new TreeNode("15");
         TreeNode t4 = new TreeNode("7");
         t2.left = t3;
         t2.right = t4;
         root.left = t1;
         root.right = t2;
        System.out.println(maxDepth(root));
    }


}
